package dynamtic;

import java.util.Arrays;

/**
 * 最长回文子序列
 *
 * @Author Jun jie Yi
 * 2022/3/28 16:31
 */
public class LongSonDp {
    public static void main(String[] args) {
        String str = "bbbab";
        int dispose = dispose(str);
        System.out.println(dispose);

    }

    public static int dispose(String str) {
        //创建数组备忘录
        int len = str.length();
        int[][] dp = new int[len][len];
        //初始化数组，他的初始值已经为 0 将对角线初始化为 1
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        // 反着遍历保证正确的状态转移 len 数字长度
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                // 状态转移方程
                if (str.charAt(i) == str.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        //打印出数组进行查看
        Arrays.stream(dp).forEach(e -> {
            System.out.println(Arrays.toString(e));
        });
        return dp[0][len - 1];
    }

}
